Search results for "Best-first search"
showing 3 items of 3 documents
Fuzzified Game Tree Search – Precision vs Speed
2012
Most game tree search algorithms consider finding the optimal move. That is, given an evaluation function they guarantee that selected move will be the best according to it. However, in practice most evaluation functions are themselves approximations and cannot be considered "optimal". Besides, we might be satisfied with nearly optimal solution if it gives us a considerable performance improvement. In this paper we present the approximation based implementations of the fuzzified game tree search algorithm. The paradigm of the algorithm allows us to efficiently find nearly optimal solutions so we can choose the "target quality" of the search with arbitrary precision --- either it is 100% (pr…
Context-Independent Scatter and Tabu Search for Permutation Problems
2005
In this paper, we develop a general-purpose heuristic for permutations problems. The procedure is based on the scatter-search and tabu-search methodologies and treats the objective-function evaluation as a black box, making the search algorithm context-independent. Therefore, our main contribution consists of the development and testing of a procedure that uses no knowledge from the problem context to search for the optimal solution. We perform computational experiments with four well-known permutation problems to study the efficiency and effectiveness of the proposed method. These experiments include a comparison with two commercially available software packages that are also based on met…
Measuring the Spatial Dispersion of Evolutionary Search Processes: Application to Walksat
2002
In this paper, we propose a simple and efficient method for measuring the spatial dispersion of a set of points in a metric space. This method allows the quantifying of the population diversity in genetic algorithms. It can also be used to measure the spatial dispersion of any local search process during a specified time interval. We then use this method to study the way Walksat explores its search space, showing that the search for a solution often includes several stages of intensification and diversification.